\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{amsmath}
\title{作业二: BST排序算法的实现}
\author{冯皓 \\ 数学与应用数学（强基计划） 3210100135}
\begin{document}
\maketitle
\section{设计思路}
此次程序设计大多选自书本，自己参与了main函数和BSTSorting函数的设计。由于我们需要对\_\ arr进行乱序，于是使用了srand函数以及随机数的生成，首先我们需要验证bst排序的合理性，因此需要调用内部函数printTree来进行输出操作。为了测试函数运行的效率，我们调用clock函数来测试运行的时间。具体代码如下：
\begin{verbatim}
void BSTSorting(vector<Comparable> &_arr,int _mode){
    clock_t start_time=clock();
    int i=0;
    BinarySearchTree<int> t;
    if(_mode==0){
        for(i=0;i<_arr.size();i++){
            t.insert(_arr[i]);
        }
    }else if(_mode==1){
        int j=0;
        vector<Comparable> b;
        for(j=_arr.size();j>0;j--){
            srand(unsigned(time(NULL)));
            int index= rand()%j;
            b.push_back(_arr[index]);
            _arr.erase(_arr.begin()+index);
        }
        _arr=b;
        for(i=0;i<b.size();i++){
            t.insert(b[i]);
        }
    }
    if(_arr.size()<20){
        t.printTree();
    }
    clock_t end_time = clock();
    cout<<"运行函数所需的时间" <<(double)(end_time-start_time)/CLOCKS_PER_SEC<<"秒" << endl;
}
\end{verbatim}
\section{测试结果}
我们先测试程序的正确性和合理性，于是输入1到10，进行顺序和乱序排列，最终输出结果如下：
\begin{verbatim}
1 2 3 4 5 6 7 8 9 10 运行函数所需的时间2.6e-05秒
1 2 3 4 5 6 7 8 9 10 运行函数所需的时间2.6e-05秒
\end{verbatim}
从中也可以看出,顺序和乱序排列对程序运行的时间影响不大，且经过多次尝试发现，时而顺序运行的时间长，时而逆序运行的时间长，这可能是因为排序数的个数不够多，数组的长度不是影响运行时间长短的主导因素。于是我们增加数组的长度。我们对数组长度为1000,4000,9000的情况进行测试，最终结果如下：
\begin{verbatim}
运行函数所需的时间0.003429秒（n=1000，顺序）
运行函数所需的时间0.001086秒（n=1000，乱序）
运行函数所需的时间0.046186秒（n=4000，顺序）
运行函数所需的时间0.007319秒（n=4000，乱序）
运行函数所需的时间0.227706秒（n=9000，顺序）
运行函数所需的时间0.029165秒（n=9000，乱序）
\end{verbatim}
进行粗略的计算估计可以知道，对于一三五组数据，我们发现$\frac{t}{n^2}$所得到的值相近，对于二四六组数据，我们发现$\frac{t}{n\log_2{n}}$所得到的值相近，由此可以得出前者时间复杂度为$O(n^2)$,后者为$O(nlogn)$
\section{内存泄漏检查}
经检查，不存在内存泄漏
\end{document}